package writtenTraining.day6;

import java.util.*;

/**
 * day6:(1)模拟+字符串逆置:NC1 大数加法
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        // 模拟 + 逆置

        // 逆置
        // 准备工作
        StringBuilder str1 = new StringBuilder(s);
        str1 =  str1.reverse();
        int len1 = str1.length();
        StringBuilder str2 = new StringBuilder(t);
        str2  = str2.reverse();
        int len2 = str2.length();
        StringBuilder ret = new StringBuilder();

        // 循环累加
        int i = 0, decade = 0;
        while(i < len1 || i < len2) {
            int target = 0;
            // 当前位置的两个数字相加
            if(i < len1) {
                target += ((str1.charAt(i))- '0');
            } 

            if(i < len2) {
                  target += ((str2.charAt(i))- '0');
            }
            // 还要加上前一位的进位
            target += decade;

            // 提炼每一位的结果
            ret.append((char)(target % 10 + '0'));

            // 保存进位
            decade = target / 10;
            i++;
        }


        // 最终把最后一位加上并且逆置
        if(decade != 0) {
            ret.append((char)(decade + '0'));
        }
        

        // 逆置返回
        return ret.reverse().toString();
    }
}




class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
  }


/**
 * day6:(2)模拟+链表逆置：NC40 链表相加(二)
 */



 class Solution1 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // 逆置处理
        ListNode h1 = listReverse(head1);
        ListNode h2 = listReverse(head2);

        // 进行累加处理
        ListNode ret = new ListNode(-1);
        ListNode cur = ret;
        int decade = 0;
        while(h1 != null || h2 != null) {
            int target = 0;
            // 累加当前位数
            if(h1 != null) {
                target += h1.val;
                h1 = h1.next;
            }
            if(h2 != null) {
                target += h2.val;
                h2 = h2.next;
            }

            // 加上前一位的进位
            target += decade;

            // 加入结果
            ListNode node = new ListNode(target % 10);
            cur.next = node;
            cur = cur.next;


            // 记录进位
            decade = target / 10;

        }

        // 最终判断还有没有进位
        if(decade != 0) {
            ListNode node = new ListNode(decade);
            cur.next = node;
            cur = cur.next;
        }

        // 最终返回逆置回来的链表
        return listReverse(ret.next);
    }

    // 链表逆置方法
    public ListNode listReverse (ListNode head) {
        // 准备工作
        ListNode prev = null , cur  = null , next = head;

        while(next != null) {
            // 首先先三个指针都各走一步
            prev = cur;
            cur = next;
            next = next.next;

            // 修改指向
            cur.next = prev;
        }

        // 最终返回的cur 就为新的头节点
        return cur;
    }
}


/**
 * day6:(3)模拟 + 无进制相加:NC10 大数乘法
 */



 class Solution2 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        // 模拟 + 无进制想加
        if(s.equals("0") || t.equals("0")) {
            return "0";
        }


        // 准备工作
        int len1 = s.length(), len2 = t.length();
        StringBuilder s1 = new StringBuilder(s);
        s1 = s1.reverse();
        StringBuilder s2 = new StringBuilder(t);
        s2 = s2.reverse();
        // 创建个位和十位的数组来计算和存储
        int[] units = new int[len1+len2];
        int[] decades = new int[len1+len2];
        StringBuilder ret = new StringBuilder();

        for(int i = 0; i < len1; i++) {
            for(int j = 0; j < len2 ; j++) {
                units[i+j] += (s1.charAt(i) - '0') * ((s2.charAt(j) - '0'));
                // 存储当前位和进制位
                if(units[i+j] > 9) {
                    decades[i+j+1] += units[i+j] / 10;
                    units[i+j] %= 10;
                }
            }
        }

        for(int i = 0; i < len1 + len2 ; i++) {
            int num = decades[i] + units[i];
            if(i == len1 + len2 - 1 && num == 0) {
                continue;
            }

            if(num > 9) {
                decades[i+1] += num / 10;
                num %= 10;
            }
            ret.append((char)(num + '0'));
        }

        return ret.reverse().toString();
    }
}